using System;
using System.Collections.Generic;
using System.Text;
using MLSharp.Classification;
using System.Linq;

namespace MLSharp.SubgroupDiscovery
{
	/// <summary>
	/// An instance that can be used to perform the SD algorithm.
	/// </summary>
	public class SDAlgorithm : IClassifier
	{
		#region Private Fields

		/// <summary>
		/// The logger for the type.
		/// </summary>
		private static readonly log4net.ILog mLogger =
			log4net.LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);

		/// <summary>
		/// The options to use when performing the SD algorithm.
		/// </summary>
		private readonly SDOptions mOptions;

		#endregion

		#region Public Constructors

		/// <summary>
		/// Creates the algorithm using the specified options
		/// </summary>
		/// <param name="options"></param>
		public SDAlgorithm(SDOptions options)
		{
			mOptions = options;
		}

		#endregion

		#region Implementation of IClassifier

		/// <summary>
		/// Classifies all the instances in the specified data set.
		/// </summary>
		/// <param name="dataSet">The data set to classify.</param>
		/// <returns>The results of classifying each instance.</returns>
		ClassificationResult[] IClassifier.Classify(IDataSet dataSet)
		{
			return FindSubgroups(dataSet);
		}

		#endregion

		#region Private Methods

		/// <summary>
		/// Gets all the possible conditions that should be evaluated based
		/// on the data in the data set.
		/// </summary>
		/// <param name="dataSet"></param>
		/// <returns></returns>
		private RuleCondition[] GetPossibleConditions(IDataSet dataSet)
		{
			List<RuleCondition> conditions = new List<RuleCondition>();

			//Loop through the data and determine which possible conditions we can have.
			for (int i=0; i < dataSet.Attributes.Count; i++)
			{
				DataAttribute attribute = dataSet.Attributes[i];

				//Skip the target attribute
				if (attribute == dataSet.Attributes[dataSet.TargetAttributeIndex])
				{
					continue;
				}

				//For discrete and valued attributes, calculate conditions of the form A=Vi, A<>Wi
				if (attribute.Type == AttributeType.Discrete || attribute.Type == AttributeType.Set)
				{
					//The positive value for the target attribute.
					string positiveValue = dataSet.Attributes[dataSet.TargetAttributeIndex].PossibleValues[mOptions.PositiveValueIndex];

					double[] positiveValues = (from instance in dataSet.Instances
					             where instance.GetStringValue(dataSet.TargetAttributeIndex) == positiveValue
					             select instance.Values[i]).Distinct().ToArray();

					//Create 'Equals' conditions for the positive values
					foreach (double value in positiveValues)
					{
						//The Equals condition.
						conditions.Add(new RuleCondition
						               	{
						               		Attribute = attribute.Name,
						               		OperatorType = ConditionOperatorType.Equals,
						               		Value = attribute.IsNumeric() ? (object)value : attribute.PossibleValues[(int)value]
						               	});
					}

					double[] negativeValues = (from instance in dataSet.Instances
											   where instance.GetStringValue(dataSet.TargetAttributeIndex) != positiveValue
											   select instance.Values[i]).Distinct().ToArray();

					//Create 'NotEquals' conditions for the negative values
					foreach (double value in negativeValues)
					{
						//The Not Equals condition.
						conditions.Add(new RuleCondition
						               	{
						               		Attribute = attribute.Name,
						               		OperatorType = ConditionOperatorType.NotEqual,
											Value = attribute.IsNumeric() ? (object)value : attribute.PossibleValues[(int)value]
										});
					}
				}

				//For continuous and discrete attributes, calculate conditions of the form 
				//A<=boundary, A>boundary, where boundary is defined as the mid point of a 
				//of the space between neighboring attribute values for positive and negative
				//cases.
				if (attribute.Type == AttributeType.Continuous || attribute.Type == AttributeType.Discrete)
				{
					//Sort the instances by the attribute
					Instance[] instances = dataSet.Instances.OrderBy(instance => instance.Values[i]).ToArray();

					//Step through the instances and identify boundaries
					for (int j=0; j < instances.Length-1; j++)
					{
						if (instances[j].Values[dataSet.TargetAttributeIndex] != 
							instances[j+1].Values[dataSet.TargetAttributeIndex])
						{
							double boundary = (instances[j].Values[i]+instances[j].Values[i])/2;

							conditions.Add(new RuleCondition
							               	{
							               		Attribute = attribute.Name,
							               		OperatorType = ConditionOperatorType.LessThanOrEqual,
							               		Value = boundary
							               	});
							
							conditions.Add(new RuleCondition
							               	{
							               		Attribute = attribute.Name,
							               		OperatorType = ConditionOperatorType.GreaterThan,
							               		Value = boundary
							               	});
						}
					}
				}
			}

			return conditions.ToArray();
		}

		/// <summary>
		/// Determines whether or not the candidate rule is relevant.
		/// </summary>
		/// <param name="candidateRule"></param>
		/// <param name="existingRules"></param>
		/// <returns>True if the new rule relevant, false otherwise.</returns>
		/// <remarks>
		/// Relevancy is determine as follows: a rule is NOT relevant if it's 
		/// covered true positives are a subset of another rule's true positives
		/// and it's false positives are a superset of another rule's false
		/// positives.
		/// </remarks>
		private static bool RuleIsRelevant(SdRule candidateRule, List<SdRule> existingRules)
		{
			//Check the rule against all existing rules.  
			foreach (SdRule existingRule in existingRules)
			{
				//If the rule is an exact duplicate, it isn't relevant.
				if (existingRule.Equals(candidateRule))
				{
					return false;
				}

				//If the candidate rule has a subset of true positives and a superset of false positives,
				//it isn't relevant.
				if (candidateRule.TruePositives.IsSubsetOf(existingRule.TruePositives) &&
					candidateRule.FalsePositives.IsSupersetOf(existingRule.FalsePositives))
				{
					return false;
				}
			}

			//If execution reaches this point, the rule is relevant.
			return true;
		}

		/// <summary>
		/// Calculates the quality score of the rule.
		/// </summary>
		/// <param name="rule"></param>
		private void CalculateQuality(SdRule rule)
		{
			rule.Quality =  rule.TruePositives.Count/(mOptions.GeneralizationFactor + rule.FalsePositives.Count);
		}

		/// <summary>
		/// Sorts the rules in a beam in decreasing order of quality.
		/// </summary>
		/// <param name="beam"></param>
		private void SortAndPruneBeam(List<SdRule> beam)
		{
			//Order the rules from highest-score to lowest score.
			beam.Sort((x, y) => y.Quality.CompareTo(x.Quality));

			//Prune rules that have become irrelevant
			for (int i=beam.Count-1; i > 0; i--)
			{
				SdRule currentRule = beam[i];

				//Only compare the rule to the rules that are superior to it.  It will
				//have already been compared to the inferior rules...
				List<SdRule> beamSubset = new List<SdRule>(beam);
				beamSubset.RemoveRange(i, beam.Count - i);

				if (!RuleIsRelevant(currentRule, beamSubset))
				{
					if (mLogger.IsDebugEnabled)
					{
						mLogger.DebugFormat("Pruning irrelevant rule: {0}.", currentRule);
					}

					beam.RemoveAt(i);
					i--;
				}
			}

			//Trim the beam to the max beam width.
			if (beam.Count > mOptions.BeamWidth)
			{
				beam.RemoveRange(mOptions.BeamWidth, beam.Count - mOptions.BeamWidth);
			}

			if (mLogger.IsInfoEnabled)
			{
				mLogger.Info("Current beam contents:");

				foreach (SdRule rule in beam)
				{
					mLogger.InfoFormat("{0}: {1}", rule.Quality, rule);
				}
			}
		}

		/// <summary>
		/// Labels the instances in the data set using the rules from the beam.
		/// </summary>
		/// <param name="dataSet"></param>
		/// <param name="beam"></param>
		/// <returns></returns>
		private ClassificationResult[] LabelInstances(IDataSet dataSet, List<SdRule> beam)
		{
			ClassificationResult[] results = new ClassificationResult[dataSet.Instances.Count];

			//These structures are used to calculate weighted relative accuracy.
			int positiveCount = dataSet.CountPositiveInstances();

			//This is used to output the total number of instances covered by at least one rule.
			int coveredInstanceCount = 0;

			for (int i = 0; i < results.Length; i++)
			{
				//Initialize the rule.  By default, an instance is not in any subgroup.
				results[i] = new ClassificationResult("", dataSet.Instances[i].ClassValue);
				results[i].PredictedClass = "";
				
				results[i].ID = dataSet.Instances[i].Label;

				for (int j=0; j < beam.Count; j++)
				{
					if (beam[j].CoversInstance(dataSet, i))
					{
						results[i].PredictedClass += j + ",";
						results[i].Explanation += beam[j] + ",";
					}
				}

				//If the instance was covered by at least one rule, count it
				if (results[i].PredictedClass != "")
				{
					coveredInstanceCount++;
				}
			}

			if (mLogger.IsInfoEnabled)
			{
				mLogger.InfoFormat("{0} [{1}%] instances were covered by the ruleset.", coveredInstanceCount, (coveredInstanceCount * 100.0)/ dataSet.Instances.Count);
				mLogger.InfoFormat("Data set contains {0} instances, {1} of which were positive.", dataSet.Instances.Count,
				                   positiveCount);
			}

			return results;
		}

		/// <summary>
		/// Populates the TruePositive, FalsePositive, and other rule properties
		/// for the initial rule.
		/// </summary>
		/// <param name="rule"></param>
		/// <param name="dataSet"></param>
		private void InitializeRule(SdRule rule, IDataSet dataSet)
		{
			rule.TotalInstanceCount = dataSet.Instances.Count;
			rule.TotalPositiveCount = dataSet.CountPositiveInstances();

			//Count the number of true and false positives for the rule.
			for (int i = 0; i < dataSet.Instances.Count; i++)
			{
				//If the rule covers the instance, it is predicting positive...
				if (rule.CoversInstance(dataSet, i))
				{
					//So count it as a true positive if it is true
					if (dataSet.Instances[i].GetStringValue(dataSet.TargetAttributeIndex) ==
						dataSet.Attributes[dataSet.TargetAttributeIndex].PossibleValues[mOptions.PositiveValueIndex])
					{
						rule.TruePositives.Add(i);
					}
					else
					{
						rule.FalsePositives.Add(i);
					}
				}
			}
		}

		/// <summary>
		/// Updates the true and false positives for the rule to account
		/// for changes in the rule criteria.
		/// </summary>
		/// <param name="rule"></param>
		/// <param name="dataSet"></param>
		public void RefreshRule(SdRule rule, IDataSet dataSet)
		{
			//Check both true and false positive instances to see if they are 
			//still covered.
			foreach (HashSet<int> instanceSet in new [] { rule.TruePositives, rule.FalsePositives} )
			{
				//This is necessary because you can't modify an enumerable while you are 
				//stepping through it.
				HashSet<int> indexesToRemove = new HashSet<int>();

				foreach (int index in instanceSet)
				{
					if (!rule.CoversInstance(dataSet, index))
					{
						indexesToRemove.Add(index);
					}
				}

				//Now remove all the instances that were identified as not being covered any longer.
				instanceSet.RemoveWhere(indexesToRemove.Contains);
			}
		}

		#endregion

		#region Public Methods

		/// <summary>
		/// Performs the SD algorithm and discovers subgroups in the specified data set.
		/// </summary>
		/// <param name="dataSet">The data.</param>
		/// <returns>The Class of the classification result is a sequential subgroup ID.</returns>
		public ClassificationResult[] FindSubgroups(IDataSet dataSet)
		{
			//This should only work if the target attribute is binary.
			if (dataSet.Attributes[dataSet.TargetAttributeIndex].Type != AttributeType.Set
				|| dataSet.Attributes[dataSet.TargetAttributeIndex].PossibleValues.Length != 2)
			{
				throw new NotSupportedException("The SD algorithm can only be applied to binary targets.");
			}

			double minSupport = mOptions.MinSupport;

			//If min support is 0, calculate it using the formula sqrt(Positives)/sizeof(DataSet)
			if (minSupport == 0)
			{
				minSupport = Math.Sqrt(dataSet.CountPositiveInstances())/dataSet.Instances.Count;
			}

			//Using "Condition" instead of "Feature" because we already have a Condition class.
			RuleCondition[] possibleConditions = GetPossibleConditions(dataSet);

			if (mLogger.IsInfoEnabled)
			{
				mLogger.InfoFormat("Extracted {0} possible conditions.", possibleConditions.Length);
			}

			List<SdRule> beam = new List<SdRule>();
			List<SdRule> currentBeam = new List<SdRule>();

			//Grab the positive value for the attribute.
			string positiveValue = dataSet.Attributes[dataSet.TargetAttributeIndex].PossibleValues[mOptions.PositiveValueIndex];

			//Initialize the beam with an empty rule that just predicts the positive case.
			SdRule initialRule = new SdRule { Class = positiveValue };

			//Populate the rule with initial values.
			InitializeRule(initialRule, dataSet);

			beam.Add(initialRule);
			currentBeam.Add(initialRule);

			bool beamChanged;

			do
			{
				beamChanged = false;

				foreach (SdRule rule in beam)
				{
					foreach (RuleCondition condition in possibleConditions)
					{
						//Skip conditions that the rule already has.
						if (rule.ConditionsList.Contains(condition))
						{
							continue;
						}

						//Create a new rule that contains the AND of the conditions.
						SdRule candidateRule = rule.Clone();
						candidateRule.ConditionsList.Add(condition);

						//Refresh the true/false positive sets, then recalculate the quality.
						RefreshRule(candidateRule, dataSet);
						CalculateQuality(candidateRule);

						//If the rule is relevant and has the required support, add it to the beam.
						if (candidateRule.TruePositives.Count / (double)dataSet.Instances.Count > minSupport &&
							RuleIsRelevant(candidateRule, currentBeam))
						{
							//If the beam is full, only add the rule if it's quality is greater than 
							//the last rule.
							if (currentBeam.Count == mOptions.BeamWidth && candidateRule.Quality <= currentBeam[currentBeam.Count-1].Quality)
							{
								continue;
							}

							currentBeam.Add(candidateRule);
							SortAndPruneBeam(currentBeam);

							beamChanged = true;
						}
					}
				}

				beam.Clear();
				beam.AddRange(currentBeam);

			} while (beamChanged);

			//Log all the rules
			if (mLogger.IsInfoEnabled)
			{
				//This is used to build the rules up into one giant log message.
				StringBuilder sb = new StringBuilder();
				sb.AppendLine("Dumping rules: ");
                
				for (int i=0; i < beam.Count; i++)
				{
					sb.AppendFormat("Rule {0} ({1}): {2}", i, beam[i].Quality, beam[i]);
					sb.AppendLine();

					//You can uncomment this line if you want to see the covered instances
					//in the log output.
					//sb.AppendFormat("Instances: ");

					//for (int j=0; j < dataSet.Instances.Count; j++)
					//{
					//    if (beam[i].CoversInstance(dataSet, j))
					//    {
					//        sb.AppendFormat("{0},", j);
					//    }
					//}
					//sb.AppendLine();
				}

				mLogger.Info(sb.ToString());
			}

			//Label each instance with a subgroup/rule ID
			ClassificationResult[] results = LabelInstances(dataSet, beam);

			return results;
		}

		#endregion
	}
}
